
import datastructurelike.ListNode;
import datastructurelike.TreeNode;

import java.util.*;

import static java.lang.Math.abs;
import static sun.swing.MenuItemLayoutHelper.max;

public class SoulutionWriteByMe {

    //最小的k个数，2021.5.7
    //add和offer区别：两者都是往队列尾部插入元素，不同的时候，当超出队列界限的时候，add（）方法是抛出异常让你处理，而offer（）方法是直接返回false
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
            ArrayList<Integer> result = new ArrayList<>();
            int length = input.length;
            if(k > length || k == 0){
                return result;
            }
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (o1, o2) -> o2.compareTo(o1));
            for (int i = 0; i < length; i++) {
                if (maxHeap.size() != k) {
                    maxHeap.offer(input[i]);
                } else if (maxHeap.peek() > input[i]) {
                    maxHeap.offer(input[i]);
                }
            }
            for (Integer integer : maxHeap) {
                result.add(integer);
            }
            return result;
        }
    // 最长无重复子串的长度
    public int maxLength (int[] arr) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();
        int max=0;
        for(int start=0,end=0;end<arr.length;end++){
            if(map.containsKey(arr[end])){
                start=Math.max(start,map.get(arr[end])+1);
            }

            max=Math.max(max,end-start+1);
            map.put(arr[end],end);
        }
        return max;
    }
    // 二分查找
    public int search (int[] nums, int target) {
        // write code here
        int start=0;
        int end=nums.length;

        while (start<=end){
            int pos=start+(end-start)/2;

            if(nums[pos]<target){
                start=pos+1;
            }else if(nums[pos]>target) {end=pos-1;}
            if(nums[pos]==target){
                return pos;
            }
        }
        return -1;
    }

    // 快速排序
    public int[] MySort (int[] arr) {
        // write code here
        arr =  quickSort(arr, 0, arr.length-1);
        return arr;
    }

    //一次排序
    public int[] quickSort(int[] arr, int low , int high){
        if(low>=high) {
            return arr;
        }

        int i=low, j = high, temp = arr[low];

        while(i<j){
            while(i<j && arr[j]>temp) {
                j--;
            }
            if(i<j) {
                arr[i++] = arr[j];
            }

            while(i<j && arr[i]<temp) {
                i++;
            }
            if(i<j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = temp;
        arr = quickSort(arr, low, i-1);
        arr = quickSort(arr, j+1, high);
        return arr;
    }

    // 括号匹配

    /**
     *
     * @param s
     * @return
     * 遍历字符串，匹配到左括号时，将对应的右括号进栈，
     * 当匹配到右括号时，弹出栈顶元素看是否一致，诺栈为空或不一致时，无效括号序列
     * 遍历完栈为空时，则为有效括号序列
     *
     */

    public boolean isValid (String s) {
        // write code here
        Stack<Character> stack = new Stack<Character>();
        for(char c : s.toCharArray()){
            if(c=='(') {
                stack.push(')');
            } else if(c=='[') {
                stack.push(']');
            } else if(c=='{') {
                stack.push('}');
            } else if(stack.empty() || stack.pop()!=c) {
                return false;
            }
        }
        return stack.empty();
    }

    // 跳台阶
    public int jumpFloor(int target) {

        int d1 = 1, d2 = 1;
        while(target-- > 1 ){
            int temp = d2;
            d2 = d2 + d1;
            d1 = temp;
        }
        return d2;

    }

    /** 链表是否有环
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */

    public boolean hasCycle(ListNode head) {
       ListNode slowPointer=head;
       ListNode quickPointer=head;
       while (quickPointer!=null && quickPointer.next!=null){
           slowPointer=slowPointer.next;
           quickPointer=quickPointer.next.next;
           if (slowPointer==quickPointer) {
               return true;
           }

       }
       return false;
    }



    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */


    /** 最近公共祖先
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here

        TreeNode result =commonNode(root,o1,o2);
        if(result == null){
            return -1;
        }
        return result.val;

    }

;    public TreeNode commonNode(TreeNode node,  int o1, int o2){
        if(node == null || node.val ==o1 || node.val == o2){
            return node;
        }
        TreeNode left = commonNode(node.left, o1, o2);
        TreeNode right = commonNode(node.right, o1, o2);
        if(left ==null){
            return right;
        }
        if(right ==null){
            return left;
        }
        return node;
    }

    // 合并有序数组
    public void merge(int A[], int m, int B[], int n) {
        //因为题目明确说了A数组足够大，所以直接在A数组操作
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;//AB合并后最后一个元素所在位置
        while(i >= 0 && j >= 0)//AB合并，谁大就先放谁
        {
            A[index --] = A[i] > B[j] ? A[i --] : B[j --];
        }
        while(j >= 0)//如果B没有遍历完，那么之间丢在A数组里面
        {
            A[index --] = B[j --];
        }

    }
    //两数之和
    //O(n)复杂度，遍历一遍，找到解就返回，没找到就放入map，key是值，value是下标加1；
    public static int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<numbers.length;i++) {
            if (map.containsKey(target - numbers[i])) {
                return new int[]{map.get(target - numbers[i]), i + 1};
            }
            map.put(numbers[i], i + 1);
        }
        return null;

    }


    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if (head == null) {
            return null;
        }
        ListNode dum = new ListNode(0);
        dum.next = head;
        ListNode slow=dum;
        ListNode quick=dum;
        for (int i = 0; i <= n; i++) {
            quick=quick.next;
        }
        while (quick != null) {
            slow = slow.next;
            quick = quick.next;
        }
        slow.next = slow.next.next;
        return dum.next;
    }

    public ArrayList<ArrayList<Integer> > print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        if (pRoot == null){
            return ans;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(pRoot);
        while (!stack1.isEmpty() || !stack2.isEmpty()){
            if (!stack1.isEmpty()){
            ArrayList<Integer>  tmp  = new  ArrayList<>();
            while (!stack1.isEmpty()){
                TreeNode p= stack1.pop();
                tmp.add(p.val);
                stack2.push(p.left);
                stack2.push(p.right);
            }ans.add(tmp);
            }
            else {
                ArrayList<Integer>  tmp  = new  ArrayList<>();
                while (!stack2.isEmpty()){
                    TreeNode p= stack2.pop();
                    tmp.add(p.val);
                    stack2.push(p.right);
                    stack2.push(p.left);
                }
                ans.add(tmp);
            }

        }
        return ans;
    }

    /**
     * 反转列表
     *
     * @param head 头
     * @return {@link ListNode}
     */
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next==null){
            return head;
        }
        ListNode pre =null;
        ListNode cur = head;

        while (cur != null) {
           ListNode tmp=cur.next;
           cur.next=pre;
           pre=cur;
           cur=tmp;
        }
        return pre;
    }
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        //用于返回最后的结果
        ArrayList<ArrayList<Integer>> res = new ArrayList();

        if(root == null) {
            return res;//如果根节点为空就返回结果
        }
        Queue<TreeNode> q = new LinkedList<TreeNode>();//用于存储每一层的节点
        q.add(root);
        while (!q.isEmpty()){
            int n=q.size();
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if(node.left !=null){
                    q.add(node.left);
                }
                if(node.right !=null){
                    q.add(node.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }

    /**
     * 超过一半的num的解决方案
     *
     * @param array 数组
     * @return int
     */
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        int times = 1;
        int candiata = array[0];
        for (int i = 1; i < array.length; i++) {
            if (times == 0) {
                candiata = array[i];
                times = 1;
            } else {
                if (candiata == array[i]) {
                    times++;
                } else {
                    times--;
                }
            }
        }
        return candiata;
    }

    /**
     * 判断平衡二叉树解决方案
     *
     * @param root 根
     * @return boolean
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!IsBalanced_Solution(root.left)){
            return false;
        }
        if(!IsBalanced_Solution(root.right)){
            return false;
        }
        int left=getHeight(root.left);
        int right=getHeight(root.right);

        return abs(left - right) <= 1;

    }

    /**
     * 获取二叉树高度
     *
     * @param root 根
     * @return int
     */
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int left=getHeight(root.left);
        int right=getHeight(root.right);
        return max(left,right)+1;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        //先创建一个哑节点
        ListNode dummy = new ListNode(0);
        //让哑节点的指针指向链表的头
        dummy.next = head;
        //开始反转的前一个节点，比如反转的节点范围是[link1，link2],
        //那么pre就是link1的前一个节点
        ListNode pre = dummy;
        ListNode end = dummy;
        while (end.next != null) {
            //每k个反转，end是每k个链表的最后一个
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            //如果end是空，说明不够k个，就不需要反转了，直接退出循环。
            if (end == null) {
                break;
            }
            //反转开始的节点
            ListNode start = pre.next;
            //next是下一次反转的头结点，先把他记录下来
            ListNode next = end.next;
            //因为end是这k个链表的最后一个结点，把它和原来链表断开，
            //这k个节点我们可以把他们看做一个小的链表，然后反转这个
            //小链表
            end.next = null;
            //因为pre是反转链表的前一个节点，我们把小链表[start,end]
            //反转之后，让pre的指针指向这个反转的小链表
            pre.next = reverse(start);
            //注意经过上一步反转之后，start反转到链表的尾部了，就是已经
            //反转之后的尾结点了，让他之前下一次反转的头结点即可（上面分析
            //过，next就是下一次反转的头结点）
            start.next = next;
            //前面反转完了，要进入下一波了，pre和end都有重新赋值
            pre = start;
            end = start;
        }
        return dummy.next;
    }

    //链表的反转
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    /**
     * 数组中第一个缺失的正数
     *
     * @param arr
     * @return int
     */
    public int minNumberdisappered (int[] arr) {
        int n =arr.length;
        // write code here

        for (int i = 0; i < arr.length; i++) {
            if(arr[i] <= 0){
                arr[i] = n+1;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            int num=arr[i];
            if (num <=n) {
                arr[num-1]=-abs(arr[num - 1]);
            }

        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) {
                return i+1;
            }
        }
        return n+1;
    }

    /**
     * 删除重复的
     *
     * @param head 头
     * @return {@link ListNode}
     */
    public ListNode deleteDuplicates_ (ListNode head) {
        if(head == null){
            return null;
        }
        // write code here
        ListNode cur = head;

        while (cur.next != null){
            if (cur.next.val== cur.val){
                cur.next=cur.next.next;
            }else {
                cur=cur.next;
            }

        }
        return head;
    }

    public ListNode deleteDuplicates (ListNode head) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy;

        while(head!=null&&head.next!=null){
            if(head.val==head.next.val){
                while(head.next!=null&&head.val==head.next.val){
                    head=head.next;
                }
                pre.next=head.next;
                head=head.next;
            }
            else{
                pre=head;
                head=head.next;
            }
        }
        return dummy.next;
    }
    public static void main(String[] args) {
        Soulution soulution = new Soulution();
        String ans=soulution.toString();
        System.out.println(ans);
    }

}
